Systems for optically scanning patterns and then analyzing the data to "recognize" the patterns are common. A typical form of optical pattern recognition is depicted in FIGS. 1 and 2 as a simplified version of the common linear or one-dimensional bar code 10. As depicted in FIGS. 1 and 2, a scanning beam 12 is scanned across the bar code 10 by a scanning device. A string of reflectance values are thereby produced which represent the transitions from bars to spaces along the scanning beam 12. Alternatively, an entire image or "snapshot" of the symbol 10 is taken by the reader. The data as reflected from the bar code 10 is then placed into a computer memory 14 on a pixel-by-pixel basis as pixel data 16, as depicted in FIG. 3, where each square in FIG. 3 represents a unique memory location. Since the data in the bar code 10 is arranged along one dimension, it does not matter whether the scanning takes place perpendicular to the bar code 10 as depicted in FIG. 1 or at an angle as depicted in FIG. 2. Similarly, it does not matter whether the pixel data 16 are located one-dimensionally or two-dimensionally within the computer memory 14 since the reader can readily analyze the data to determine the contents thereof. However, if the memory is large, includes multiple bar code images or images with significant background noise, the reader requires time consuming methods to locate and decode the bar code.
Optical Character Recognition (OCR) as it relates to the ability to "read" alphanumeric characters is another matter since the data is now related to a two-dimensional character. Thus, the problem is different if a character 18 being "scanned" is oriented in a known perpendicular direction as in FIG. 4 or skewed as in FIG. 5. While the character 18 can be scanned on a line-by-line basis by a raster scanning technique, it is easier and most common to simply view the character 18 two-dimensionally with, for example, a charge coupled device (CCD) camera which provides pixel data 16' within a computer memory 14 in the manner depicted in FIG. 6.
The contents of the computer memory 14 must then be analyzed on a correlated line-by-line basis as depicted in FIG. 7. The prior art techniques for analyzing the data from each line 20 of the memory 14 are complex and time-consuming, particularly if multiple fonts are to be "recognized" and orientations other than perpendicular are to be included. As can be appreciated, the prior art methodology of character recognition from the data 16' on a horizontal and vertical basis (i.e., line-by-line forward and backward and across each line pixel position-by-pixel position) cannot be accomplished in real-time. That is, the data must be scanned and then analyzed in a process that can literally take minutes for a standard page of characters.
While suffering from some of the processing intensive limitations of OCR, two-dimensional symbols or bar codes as depicted in FIG. 8 allow much more data to be represented in a much smaller space. FIG. 8 shows a so-called "Code-One" type of bar code 22. Code-One bar codes are of various types; but, each contains two components--an orientation pattern 24 and attached 2D data 26. A portion of the orientation pattern 24 from the bar code 22 of FIG. 8 is shown in FIG. 9. The orientation pattern 24 comprises a central portion 28 that defines the type of Code-One bar code present and is uniquely identifiable and locatable as to orientation; and, peripheral portions 30 that define the extents and sizing of the 2D data 26.
The central portion 28 has a plurality of "vertical" edges 32 and "horizontal" edges 34 when the bar code 22 is in its proper orientation, and the edges are in a fixed relationship to one another. Thus, regardless of the orientation, if the vertical and horizontal edges can be found, the type of bar code 22 can be determined, its orientation can be determined, and the 2D data 26 can be interpreted.
FIG. 10 shows another two-dimensional symbol, namely a PDF 417 symbol 40. The orientation pattern consists of start and stop patterns 42 and 44. The start and stop patterns include very large or wide bars relative to the rest of the symbol, 46 and 48, respectively. The bars 46 and 48 can be found within the stored image (e.g., by locating their elongated edges), and thus the position and type of the bar code 40 can be determined. Thereafter, three rows of bars and spaces 39 positioned between the start and stop patterns 42 and 44 can be decoded.
Prior art techniques for locating and decoding two-dimensional symbols still approach the problem in the same manner as with OCR or alphanumeric data. All the pixels of the scanned 2D image are stored in a computer memory and then the data is analyzed on a line-by-line basis. As compared with recognizing an "H" surrounded by white space, a reader has difficulty recognizing one of many orientation patterns 24 within the bar code 22 as in FIG. 8, or the start and stop patterns 42 and 44 within the bar code 40 as shown in FIG. 10, particularly if the patterns must be quickly located.
When scanning or imaging two-dimensional bar codes at a point of sale, work station, or the like, a recognition process can take minutes to accomplish. Readers may also have difficulty in quickly locating and decoding traditional bar codes. The finding and decoding of the data must take place in real-time or close to real-time. A typical consumer requirement is to have the data available in one second or less. Therefore, it is desirable to provide a method of analyzing optically stored data associated with machine-readable symbols or characters which can find and decode the data in real-time or close to real-time.
Most two-dimensional imagers or readers first store an image or "snapshot" of the machine-readable symbol. Thereafter, the reader attempts to locate the image of the symbol within the stored image. One method of locating a symbol image within the stored image attempts to locate an edge of a bar of the symbol, which is described in detail in U.S. patent application Ser. No. 08/607,100, entitled "Method and Apparatus for Accurately Locating Data Regions in Stored Images of Symbols," filed Feb. 26, 1996, and assigned to the assignee of the present invention. Other robust methods of locating symbol images within stored images are described in detail in U.S. patent application Ser. No. 08/687,659, entitled "Time-Efficient Method of Analyzing Imaged Input Data to Locate Two-Dimensional Machine-Readable Symbols or Other Linear Images Therein," filed Jul. 26, 1996, U.S. patent application Ser. No. 08/602,624, entitled "Method and Apparatus for Locating and Decoding Machine-Readable Symbols," filed Feb. 16, 1996, and U.S. patent application Ser. No. 08/654,925, entitled "Method and Apparatus for Locating an Decoding Machine-Readable Symbols, Including Data Matrix Symbols," filed May 29, 1996, all of which are assigned to the assignee of the present invention. These methods, however, often require significant processing time. As a result, many of these methods require high-speed, and costly, processors, or undesirable delays with slower processors.